<!DOCTYPE HTML>

<!-- 
Strata by HTML5 UP
html5up.net | @n33co
Free for personal and commercial use under the CCA 3.0 license (html5up.net/license)
-->
<html>
	<head>
		<title>DSU &middot; Blog for Ysc</title>
		<meta charset="utf-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1" />
		<meta name="author" content="Your name">
		<meta name="description" content="Describe your website">
		<meta http-equiv="content-language" content="en-us" />

		
		<meta name="og:site_name" content="Blog for Ysc">
		<meta name="og:title" content="DSU">
		<meta name="og:url" content="https://yeeeesc.gitee.io/post/dsu/">
		
		<meta name="og:image" content="https://yeeeesc.gitee.io/images/avatar.jpg">
		
		

		<meta name="generator" content="Hugo 0.69.2" />

		<!--[if lte IE 8]><script src='https://yeeeesc.gitee.io/js/ie/html5shiv.js'></script><![endif]-->
		<link rel="stylesheet" type="text/css" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css">
		<link rel="stylesheet" href="https://yeeeesc.gitee.io/css/main.css" />
		<!--[if lte IE 8]><link rel="stylesheet" href="https://yeeeesc.gitee.io//css/ie8.css"><![endif]-->

		
		
	</head>

	<body id="top">
		<!-- Header -->
<header id="header">
	
	<a href="https://yeeeesc.gitee.io/" class="image avatar"><img src="https://yeeeesc.gitee.io/images/avatar.jpg" alt="" /></a>
	
	
		<h1><strong>I&rsquo;m Strata</strong>, a super simple<!-- raw HTML omitted --> responsive site template freebie<!-- raw HTML omitted --> crafted by <a href="//html5up.net">HTML5 UP</a>.</h1>
	

	
		<nav id="sidebar">
			<ul>
			
				<li><a href="https://yeeeesc.gitee.io/">Home</a></li>
			
				<li><a href="https://yeeeesc.gitee.io/post/">Blog</a></li>
			
			</ul>
		</nav>
	
</header>


		<!-- Main -->
		<div id="main">
			
	<span>
		<h1>DSU</h1>

		<i class="fa fa-calendar"></i>&nbsp;&nbsp;
<time datetime="2020-10-19 13:39:46 &#43;0200 &#43;0200">2020-10-19</time>&nbsp;&nbsp;




    
    
        <i class="fa fa-folder"></i>&nbsp;&nbsp;
        
        <a class="article-category-link" href="https://yeeeesc.gitee.io/categories/data-structure">Data Structure</a>
        
        
    



   
   


	</span>

	<p>
	    <h3 id="step-1-dsu简介">Step 1. DSU简介</h3>
<p>一个 DSU(Disjoint Set Union)数据结构可以用来维护图形连接组件的数据，并快速查询它们。有两种操作：</p>
<p><code>① dsu.find(node x)</code>
找到元素 x 所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合。</p>
<p><code>② dsu.union(node x, node y)</code>
把元素 x 和元素 y 所在的集合合并，要求 x和 y 所在的集合不相交，如果相交则不合并。</p>
<p>为了实现这一点，我们跟踪父结点，它会记录同一连接节点中较小结点的所在的集合。如果结点是它自己的父结点，我们将其称为连接结点的领导者。</p>
<h3 id="step-2-代码实现">Step 2. 代码实现</h3>
<p>我们使用两种技术来提高运行时的复杂性：<code>路径压缩和按秩合并</code>。</p>
<p>路径压缩涉及将 find 函数中的 x=parent[x] 更改为 parent[x]=find(parent[x])。
按秩合并涉及到将发现的工作量平均分配给领导者。每当 dsu.union(x, y) 时，我们都有两个领导者 xr，yr，并且我们要选择是要 parent[x]=yr 还是 parent[y]=xr。我们选择有更多子节点的领导者作为领导者。</p>
<p>具体地说，rank 的含义是 x 的跟随者少于 2 ^ rank[x]，这个策略可以作为 dsu.find 中的递归循环可中的界限。</p>
<pre><code>class DSU {
public:
	DSU(int size) {
        parent = new int[size];
        for (int i = 0; i &lt; size; i++) parent[i] = i;
        rank = new int[size];
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    bool unions(int x, int y) {
        int xr = find(x), yr = find(y);
        if (xr == yr) {
            return false;
        } else if (rank[xr] &lt; rank[yr]) {
            parent[xr] = yr;
        } else if (rank[xr] &gt; rank[yr]) {
            parent[yr] = xr;
        } else {
            parent[yr] = xr;
            rank[xr]++;
        }
        return true;
    }
private:
	int* parent;
    int* rank;
};
</code></pre><h3 id="step-3-例题应用">Step 3. 例题应用</h3>
<h6 id="684-冗余连接leetcodehttpsleetcode-cncomproblemsredundant-connection"><a href="https://leetcode-cn.com/problems/redundant-connection/">684. 冗余连接(LeetCode)</a></h6>
<p>在本问题中, 树指的是一个连通且无环的无向图。</p>
<p>输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, &hellip;, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。</p>
<p>结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u &lt; v，表示连接顶点u 和v的无向图的边。</p>
<p>返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u &lt; v。</p>
<pre><code>输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
  1
 / \
2 - 3
</code></pre><p><strong>Answer:</strong></p>
<pre><code>class DSU{
	//...
}

class Solution {
public:
    int MAX_EDGE_VAL = 1000;

    vector&lt;int&gt; findRedundantConnection(vector&lt;vector&lt;int&gt;&gt;&amp; edges) {
        DSU* dsu = new DSU(MAX_EDGE_VAL + 1);
        for (auto edge: edges) {
            if (!dsu-&gt;unions(edge[0], edge[1])) return edge;
        }
        return vector&lt;int&gt;();
    }
};
</code></pre>
	</p>

	<div id="disqus_thread"></div>
<script type="application/javascript">
    var disqus_config = function () {
    
    
    
    };
    (function() {
        if (["localhost", "127.0.0.1"].indexOf(window.location.hostname) != -1) {
            document.getElementById('disqus_thread').innerHTML = 'Disqus comments not available by default when the website is previewed locally.';
            return;
        }
        var d = document, s = d.createElement('script'); s.async = true;
        s.src = '//' + "spf13" + '.disqus.com/embed.js';
        s.setAttribute('data-timestamp', +new Date());
        (d.head || d.body).appendChild(s);
    })();
</script>
<noscript>Please enable JavaScript to view the <a href="https://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="https://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>

		</div>

		<!-- Footer -->
<footer id="footer">
	<ul class="icons">
		
		
		
		<li><a href="//twitter.com/spf13" target="_blank" class="icon fa-twitter"><span class="label">Twitter</span></a></li>
		
		
		<li><a href="//github.com/spf13" target="_blank" class="icon fa-github"><span class="label">GitHub</span></a></li>
		
		
		<li><a href="//gitlab.com/spf13" target="_blank" class="icon fa-gitlab"><span class="label">GitLab</span></a></li>
		
		
		
		
		
		<li><a href="https://yeeeesc.gitee.io/#contact-form" class="icon fa-envelope-o"><span class="label">Email</span></a></li>
		
		
		<li><a href="https://yeeeesc.gitee.io/index.xml" class="icon fa-rss" type="application/rss+xml"><span class="label">RSS</span></a></li>
		
	</ul>

	<ul class="copyright">
		
		<li>© John Doe</li>
		
		<li>Design: <a href="//html5up.net">HTML5 UP</a></li>
		
		<li>Demo Images: <a href="//unsplash.com/">Unsplash</a></li>
		
	</ul>
</footer>

<!-- Scripts -->
<script src="https://yeeeesc.gitee.io/js/jquery.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/jquery.poptrox.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/skel.min.js"></script>
<script src="https://yeeeesc.gitee.io/js/util.js"></script>

<script src="https://yeeeesc.gitee.io/js/main.js"></script>





	</body>
</html>
